//
// Created by 周智超 on 2020/6/9.
//

#ifndef STRUCTURE_STACK_QUEUE_H
#define STRUCTURE_STACK_QUEUE_H
#include "normal.h"

typedef struct
{
    int data[maxSize];
    int top;
} SqStack;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;

typedef struct
{
    int data[maxSize];
    int front;
    int rear;
}SqQueue;

typedef struct QNode{
    int data;
    struct QNode *next;
}QNode ;

typedef struct {
    QNode *front;
    QNode *rear;
}LiQueue;

void initStack(SqStack &l)
{
    l.top = -1;
}

int isEmpty(SqStack &l)
{
    if(l.top == -1)
    {
        return 1;
    }
    return 0;
}

int push(SqStack &l, int x)
{
    if(l.top == maxSize - 1) {
        return 0;
    }
    ++(l.top);
    l.data[l.top] = x;
    return 1;
}

int pop(SqStack &l, int &x)
{
    if(l.top == -1) {
        return 0;
    }
    x = l.data[l.top];
    --(l.top);
    return 1;
}

void initLStack(LNode *&lst)
{
    lst = (LNode *)malloc(sizeof(LNode));
    lst->next = NULL;
}

int isLEmpty(LNode *&lst)
{
    if(lst->next == NULL)
    {
        return 1;
    }
    return 0;
}

int lPush(LNode *&lst, int x)
{
    LNode *tmp;
    tmp = (LNode *)malloc(sizeof(LNode));
    tmp->data = x;
    tmp->next = lst->next;
    lst->next = tmp;
    return 1;
}

int lPop(LNode *&lst, int &x)
{
    LNode *tmp;
    if(lst->next == NULL)
    {
        return 0;
    }
    tmp = lst->next;
    x = tmp->data;
    lst->next = tmp->next;
    free(tmp);
    return 1;
}

int getPriority(char a)
{
    if (a == '*' || a == '/')
    {
        return 2;
    }
    return 1;
}

int calc(int a, int b, char op, int &e)
{
    int success = 1;
    switch (op) {
        case '+':
            e = a + b;
            break;
        case '-':
            e = a - b;
            break;
        case '*':
            e = a * b;
            break;
        case '/':
            if(b==0) {
                success = 0;
                break;
            }
            e = a / b;
            break;
        default:
            success = 0;
            break;
    }
    return success;
}

int calcByStack(char s1[],int  &top1, int s2[], int &top2)
{
    char op;
    int num1, num2, success, tempResult;
    op = s1[top1--];
    num2 =  s2[top2--];
    num1 = s2[top2];
    success = calc(num1, num2, op, tempResult);
    if(success == 0)
    {
        return success;
    }
    s2[top2] = tempResult;
    return success;
}


int calcPrefix(char prefix[], int len, int &result)
{
    int s1[maxSize]; int top1 =-1;
    int i = len - 1;
    int num1, num2, temp;
    int flag =1;
    for(; i >= 0; i--)
    {
        if('0' <= prefix[i] && prefix[i] <= '9')
        {
            s1[++top1] = prefix[i] - '0';
        }
        else
        {
            num1 = s1[top1--];
            num2 = s1[top1--];
            flag = calc(num1, num2, prefix[i], temp);
            if(flag == 0)
            {
                return flag;
            }
            s1[++top1] = temp;
        }
    }
    result = s1[top1];
    return flag;
}

int calcSuffix(char suffix[], int len, int &result)
{
    int s2[maxSize]; int top1 = -1;
    int i = 0;
    int num1, num2, temp;
    char op;
    int flag = 1;
    while (i < len)
    {
        if('0' <= suffix[i] && suffix[i] <= '9')
        {
            s2[++top1] = suffix[i] - '0';
        }
        else if(suffix[i] == '+' ||
        suffix[i] == '-' ||
        suffix[i] == '*' ||
        suffix[i] == '/')
        {
            num2 = s2[top1--];
            num1 = s2[top1];
            flag = calc(num1, num2, suffix[i], temp);
            if(flag == 0)
            {
                return flag;
            }
            s2[top1] = temp;
        }
        else {
            return 0;
        }
        i++;
    }
    result = s2[top1];
    return flag;

}

int calcInfix(char infix[], int &result)
{
    char s1[maxSize]; int top1 = -1;
    int s2[maxSize]; int top2 = -1;
    int i = 0;
    int success = 1;
    while (infix[i] != '\0')
    {
        if('0' <= infix[i] && infix[i] <= '9')
        {
            s2[++top2] = infix[i] - '0';
            i++;
        }
        else if(infix[i] == '(')
        {
            s1[++top1] = '(';
            i++;
        }
        else if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/')
        {
            if(top1==-1 || s1[top1] == '(' || getPriority(infix[i]) > getPriority(s1[top1]))
            {
                s1[++top1] = infix[i];
                i++;
            }
            else
            {
                success = calcByStack(s1, top1, s2, top2);
                if(success == 0)
                {
                    return success;
                }
            }
        }
        else if(infix[i] == ')')
        {
            while (s1[top1] != '(')
            {
                success = calcByStack(s1, top1, s2, top2);
                if(success == 0)
                {
                    return success;
                }
            }
            top1--;
            i++;
        }
    }
    while (top1 != -1)
    {
        success = calcByStack(s1, top1, s2, top2);
        if(success == 0)
        {
            return success;
        }
    }
    result = s2[0];
    return success;
}


void infix2Prefix(char infix[], int len, char s2[], int &top2)
{
    char s1[maxSize]; int top1 = -1;
    int i = len -1;
    while (i >= 0)
    {
        if('0' <= infix[i] && infix[i] <= '9')
        {
            s2[++top2] = infix[i];
            i--;
        }
        else if(infix[i] == ')')
        {
            s1[++top1] = infix[i];
            i--;
        }
        else if(infix[i] == '*' ||
        infix[i] == '/' ||
        infix[i] == '+' ||
        infix[i] == '-')
        {
            if(top1==-1 || s1[top1] == ')' || getPriority(infix[i]) >= getPriority(s1[top1]))
            {
                s1[++top1] = infix[i];
                i--;
            }
            else
            {
                s2[++top2] = s1[top1--];
            }
        }
        else  if(infix[i] == '(')
        {
            while (s1[top1] != ')')
            {
                s2[++top2] = s1[top1--];
            }
            i--;
            top1--;
        }
    }
    while (top1 != -1)
    {
        s2[++top2] = s1[top1--];
    }
    for(int a = 0, b = top2; a != b; a++,b--)
    {
        char temp= s2[a];
        s2[a] = s2[b];
        s2[b] = temp;
    }
}

void in2suffix(char infix[], char s2[], int &top2)
{
    char s1[maxSize]; int top1 = -1;
    int i = 0;
    while (infix[i] != '\0')
    {
        if(infix[i] >= '0' && infix[i] <= 'j')
        {
            s2[++top2] = infix[i];
            i++;
            continue;
        }
        if(infix[i] == '(')
        {
            s1[++top1] = infix[i];
            i++;
        }
        else if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            if(top1 == -1 || s1[top1] == '(' || getPriority(infix[i]) > getPriority(s1[top1]))
            {
                s1[++top1] = infix[i];
                i++;
            } else {
                s2[++top2] = s1[top1];
                top1--;
            }
        } else if(infix[i] == ')') {
            while (s1[top1] != '(')
            {
                s2[++top2] = s1[top1];
                top1--;
            }
            top1--;
            i++;
        }
    }
    while (top1 != -1)
    {
        s2[++top2] = s1[top1];
        top1--;
    }
    s2[top2+1] = '\0';
}


int ioLegal(char io[])
{
    int times = 0;
    int i = 0;
    for(; io[i] != '\0'; i++)
    {
        if(io[i] == 'I')
        {
            times++;
        } else {
            times--;
        }
        if(times < 0)
        {
            return 0;
        }
    }
    if(times != 0)
    {
        return 0;
    }
    return 1;
}





void initTailQueue(LNode *&tq)
{
    tq = (LNode *)malloc(sizeof(LNode));
    tq->next = tq;
}

int deTailQueue(LNode *&tq, int &e)
{
    if(tq->next == tq)
    {
        return 0;
    }
    LNode *head = tq->next->next;
    tq->next->next = head->next;
    e = head->data;
    if(head == tq) // 当出队最后一个元素则将tail设置为头节点
    {
        tq = tq->next;
    }
    free(head);
    return 1;
}

void enTailQueue(LNode *&tq, int e)
{
    LNode *s = (LNode*)(malloc(sizeof(LNode)));
    s->data = e;
    s->next = tq->next;
    tq->next = s;
    tq = s;
}

typedef struct TagQueue{
    int data[maxSize];
    int front;
    int rear;
    int flag;
} TagQueue;

void initTagQueue(TagQueue *&tq)
{
    tq = (TagQueue*)malloc(sizeof(TagQueue));
    tq->flag = 0;
    tq->front = 0;
    tq->rear = 0;
}

int enTagQueue(TagQueue *&tq, int e)
{
    if(tq->flag == 1 && tq->front == tq->rear)
    {
        return 0;
    }
    tq->rear = (tq->rear + 1) % maxSize;
    tq->data[tq->rear] = e;
    tq->flag = 1;
    return 1;
}

int deTagQueue(TagQueue *&tq, int &e)
{
    if(tq->flag == 0)
    {
        return 0;
    }
    tq->front = (tq->front + 1) % maxSize;
    e = tq->data[tq->front];
    if(tq->front == tq->rear)
    {
        tq->flag = 0;
    }
    return 1;
}

int bracketMatch(char *s)
{
    int stack[maxSize];
    int top = -1;
    int i = 0;
    char currentDelimit = 0;
    while (s[i] != '\0')
    {
        if(s[i] == 39 || s[i] == 34)
        {
            if(currentDelimit != 0)
            {
                currentDelimit = 0;
            }
            else {
                currentDelimit = s[i];
            }
        }
        else if(currentDelimit != 0)
        {
            i++;
            continue;
        }
        else if(s[i] == '(' || s[i] == '[' || s[i] == '{')
        {
            stack[++top] = s[i];
        }
        else
        {
            if(top == -1)
            {
                return 0;
            }
            char expected;
            switch (s[i]) {
                case ')':
                    expected = '(';
                    break;
                case ']':
                    expected = '[';
                    break;
                default:
                    expected = '{';
                    break;
            }
            if(expected != stack[top])
            {
                return 0;
            }
            top--;
        }
        i++;
    }
    if(top == -1)
        return 1;
    return 0;
}

#endif //STRUCTURE_STACK_QUEUE_H
